class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> left_max(height.size(), 0);
        vector<int> right_max(height.size(), 0);
        left_max[0] = height[0];
        right_max[height.size()-1] = height[height.size()-1];
        int sum = 0;
        
        for(int i = 1, j = height.size()-2; i < height.size()-1 && j > 0; ++i, --j)
        {
            left_max[i] = max(left_max[i-1], height[i]);
            right_max[j] = max(right_max[j+1], height[j]);
        }

        for(int i = 1, j = height.size()-2; i < height.size()-1 && j > 0; ++i, --j)
        {
            cout << left_max[i] << " " << right_max[i] << " " << height[i] << endl;
        }


        // reverse(right_max.begin(), right_max.end());
        for(int i = 1; i < height.size()-1; i++)
        {
            int v = min(left_max[i], right_max[i]) - height[i];
            if(v > 0)
            {
                sum += v;
            }
            else
            {
                sum += 0;
            }
        }

        return sum;
    }
};


// class Solution {
// public:
//     int trap(vector<int>& height) {
//         int left = 0;
//         int right = height.size()-1;
//         int left_max = 0;
//         int right_max = 0;
//         int sum = 0;

//         while(left < right)
//         {
//             if(height[left] < height[right])
//             {
//                 left_max = max(left_max, height[left]);
//                 sum += left_max-height[left];
//                 left++;
//             }
//             else
//             {
//                 right_max = max(right_max, height[right]);
//                 sum += right_max-height[right];
//                 right--;
//             }
//         }

//         return sum;
//     }
// };

// 核心思想: 每根柱子能够接住的雨水为 min(左边最大柱子高度, 右边最大柱子高度)-当前柱子高度

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> map;
        map.insert({'I', 1});
        map.insert({'V', 5});
        map.insert({'X', 10});
        map.insert({'L', 50});
        map.insert({'C', 100});
        map.insert({'D', 500});
        map.insert({'M', 1000});

        int result = 0;
        for(int i = 1; i < s.size(); ++i)
        {
            if(map[s[i-1]] >= map[s[i]])
            {
                result += map[s[i-1]];
            }
            else
            {
                result -= map[s[i-1]];
            }
        }

        result += map[s[s.size()-1]];

        return result;
    }
};